/**
 * [96] 不同的二叉搜索树
 * 思路：
 * # 假设 1～n 构成的不同二叉搜索树有 F(n) 种
 * # 对于根节点可选：1～n 共 n 种
 * # 不同根节点对应种数为 G(i,n) = F(i-1)*F(n-i)
 * # 对 n 种情况求和
 * @format
 * @lc app=leetcode.cn id=96 lang=javascript
 */

// @lc code=start
/**
 * @param {number} n
 * @return {number}
 */
// 通项公式

// 递归 + 哈希
const map = [1, 1, 2]
var numTrees = function (n) {
    if (map[n]) return map[n]
    map[n] = 0
    for (let i = 1; i <= n; i++) {
        map[n] += numTrees(i - 1) * numTrees(n - i)
    }
    return map[n]
}
// numTrees(19)
// console.log(map)
// 递归
/* var numTrees = function (n) {
    if (n == 0 || n == 1) return 1
    if (n == 2) return 2
    let count = 0
    for (let i = 1; i <= n; i++) {
        let left = numTrees(i - 1)
        let right = numTrees(n - i)
        count += left * right
    }
    return count
} */
// @lc code=end
